#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


 //Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     };
 
 //判断B是否是A的子结构
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==NULL||B==NULL){
            return false;
        }
        bool isLeft = isSubStructure(A->left,B);
        bool isRight = isSubStructure(A->right,B);
        if(isLeft||isRight){
            return true;
        }
        else{
            //对A和B从头节点开始遍历
            return func(A,B);
        }
    }
    //遍历A和B，判断B从头节点是否是A的子结构
    bool func(TreeNode* A,TreeNode* B){
        if(B==NULL){
            return true;
        }
        if(A!=NULL&&B!=NULL&&(A->val==B->val)){
            bool left = func(A->left,B->left);
            bool right = func(A->right,B->right);
            return left&&right;
        }
        else{
            return false;
        }
    }
};

int main(){
    Solution S;
    TreeNode* head1 = new TreeNode(3);
    head1->left = new TreeNode(4);
    head1->right = new TreeNode(5);
    head1->left->left = new TreeNode(1);
    head1->left->right = new TreeNode(2);
    TreeNode* head2 = new TreeNode(4);
    head2->left = new TreeNode(1);
    cout<<S.isSubStructure(head1,head2)<<endl;
}
